package sort;

//插入排序
//稳定的排序
public class InsertSort {
	public static void insertSort(int[] arr) {
		int n=arr.length;
		if(n==0||n==1) return ;
		for(int i=1;i<n;i++) {
			int tmp=i;
			while(tmp>0) {
				if(arr[tmp-1]>arr[tmp]) {
					Swap.swap(arr, tmp-1, tmp);
					tmp--;
				}
				else {
					break;
				}
			}
		}
	}
	public static void main(String[] args) {
		int[] arr=new int[]{9,8,7,6,5,4,3,2,1};
		insertSort(arr);
		for(int x:arr) 
			System.out.print(x+" ");
	}
}
